package leetcode.D400.T323;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-18 22:32:34 星期五
 */
class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] uf = initUF(n);
        for (int i=0; i<edges.length; ++i)
            unionFather(uf, edges[i][0], edges[i][1]);
        return getGroup(uf);
    }

    private int[] initUF(int n) {
        int[] uf = new int[n];
        for (int i=0; i<n; ++i)
            uf[i] = i;
        return uf;
    }

    private int getFather(int[] uf, int a) {
        if (a == uf[a])
            return a;
        int fa = getFather(uf, uf[a]);
        uf[a] = fa;
        return fa;
    }

    private void unionFather(int[] uf, int a, int b) {
        int fa = getFather(uf, a), fb = getFather(uf, b);
        uf[fa] = fb;
    }

    private int getGroup(int[] uf) {
        int num = 0;
        for (int i = 0; i < uf.length; i++) {
            if (uf[i] == i)
                num++;
        }
        return num;
    }
}